package com.xy6.algo.force;

/**
 * 蛮力法求解最近点对
 * 
 * 最近对问题描述的就是在包含n个端的集合中找到距离最近的两个点，
 * 当然问题也可以定义在多维空间中，但是这里只是跟随书上的思路实现了二维情况下的最近对问题。
 * 假设所有讨论的点是以标准的笛卡尔坐标形式（x，y）给出的，
 * 那么在两个点Pi=(Xi，Yi)和Pj=（Xj，Yj）之间的距离是标准的欧几里得距离：
 * 	d(Pi,Pj)=sqrt( (X1-X2)2+(Y1-Y2)2 )
 * 
 * 时间复杂度为：O(n^2)
 * 
 * @author zhang
 * @since 2017-12-23
 */
public class CloestPoints {

	public static void main(String[] args){
		int[] x = new int[]{22,32,63,75,105};
		int[] y = new int[]{11,8,7,4,3};
		
		System.out.println(calc(x, y));
	}
	
	/**
	 * 查找n个点中距离最近的两个点
	 * 
	 * @param x
	 * @param y
	 */
	public static String calc(int[] x, int[] y){
		double min = -1d;
		int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
		int n = x.length;
		double dis = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				if(min < 0){
					min = Math.pow(x[i] - x[j], 2) + Math.pow(y[i] - y[j], 2);
					x1 = x[i];
					y1 = y[i];
					x2 = x[j];
					y2 = y[j];
					continue;
				}
				dis = Math.pow(x[i] - x[j], 2) + Math.pow(y[i] - y[j], 2);
				if(dis < min){
					min = dis;
					x1 = x[i];
					y1 = y[i];
					x2 = x[j];
					y2 = y[j];
				}
			}
		}
		return String.format("%d,%d %d,%d", x1, y1, x2, y2);
	}
	
}
